# -*- coding: utf-8 -*-
from random import uniform
from time import clock
from insertionSort import insertionSort
from bubbleSort import bubbleSort
from mergesort import mergeSort
from heapsort import *
from mergeSort import *
from quickSort import *
import math
import sys

'''
Ao correr o Quicksort dava um erro "maximum recursion depth exceeded".
com o "setrecursionlimit" defenimos um limite de recursividade.
'''
sys.setrecursionlimit(999999)

def printGraph(numAlg):
    '''
    Metodo que contrói o grafico
    Parametros de entrada: 
        numAlg - numero do algoritmo escolhido
    '''
    Z = [1] + range(50, 1050, 50)
    T = []
    M = 25 
    # M é número de testes a efetuar para cada "conjunto de dados" 
    for n in Z:
        A = [ uniform(0.0,1.0) for k in xrange(n)]
        tempos = []
        for k in range(M):
            t1 = clock()
            if numAlg == 1:
                insertionSort(A)
            elif numAlg == 2:
                bubbleSort(A)
            elif numAlg == 3:
                #A.insert(0, sys.maxint)
                HeapSort(A)
            elif numAlg == 4:
                MergeSort(A, 0, len(A) - 1)
            elif numAlg == 5:
                QuickSort(A)
            t2 = clock()
            tempos.append(t2-t1)
        # Cálculo da média dos tempos de execução
        media = reduce(lambda x, y: x + y, tempos) / len(tempos)
        print "Tempo ", media
        # Cálculo da variância
        var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
        T.append((n,media, var))
    #X array com o numero de dados
    X = [n for n, media, var in T]

    #Y array com a media obtida
    Y = [media for n, media, var in T]

    # se o algoritmo for 1(Insetion Sort) ou 2(Bubble Sort) ou 5(QuickSort) o crescimento teorico será de n² caso contrario (n*log(n))
    if numAlg == 1 or numAlg == 2 or numAlg == 5:
        Z = [n**2 * (T[len(T) - 1][1] / T[len(T) - 1][0]**2) for n, media, var in T]
    elif numAlg == 3 or numAlg == 4:
        Z = [n*math.log(n,2) / ((T[len(T)-1][0]) * math.log(T[len(T)-1][0]))*(T[len(T) - 1][1]) for n, media, var in T]

    import matplotlib.pyplot as plt
    plt.grid(True)
    plt.ylabel(u'T(n) - tempo de execução médio em segundos')
    plt.xlabel(u'n - número de elementos')
    plt.plot(X,Y,'rs', label="resultado experimental")
    plt.plot(X,Z,'b^', label=u"previsão teórica")
    plt.legend()
    plt.show()

def main():
    #Faz o print do menu para o utilizador escolher qual o algoritmo a analisar.
    print '*********************\n* 1- Insertion Sort *\n* 2- Bubble Sort    *\n* 3- Heapsort       *\n* 4- Merge Sort     *\n* 5- Quicksort      *\n*********************'
    #pede para o utilizador escolher o algoritmo inserindo um numero de 1 a 5.
    #Chamando em seguida o metodo para desenhar o grafico correspondente.
    escolha = input("Qual o algoritmo que pretende analisar? ")
    print "Escolheu o algoritmo", escolha
    if escolha == 1:
        printGraph(1)
    elif escolha == 2:
        printGraph(2)
    elif escolha == 3:
        printGraph(3)
    elif escolha == 4:
        printGraph(4)
    elif escolha == 5:
        printGraph(5)
    else:
        print "Escolha um numero de 1 a 5"
        main()
    pass
pass
main()